package Sort;

/**
 * @author zhangmin
 * @create 2022-05-17 15:01
 * 215. 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 */
public class QuickSelect {
    //快排的复用
    int partition(int[] nums,int l,int r){
        if (r==l) return l;
        int p=nums[l];
        int i=l,j=r+1;
        while (true){
            // 保证 nums[l..i] 都小于 p
            while (nums[++i]<p){
                if (i==r)break;
            }
            while (nums[--j]>p){
                if (j==l) break;
            }
            if (i>=j) break;
            swap(nums,i,j);
        }
        swap(nums,j,l);
        return j;
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        k=nums.length-k;
        while (left<=right){
            int p=partition(nums,left,right);
            if (p<k){
                left=p+1;
            }else if (p>k){
                right=p-1;
            }else {
                return nums[p];
            }
        }
        return -1;
    }
}
